//
//  MaxProfit.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/10.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  309. 最佳买卖股票时机含冷冻期   tag:动态规划

import UIKit
/*
 309. 最佳买卖股票时机含冷冻期
 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
 示例:

 输入: [1,2,3,0,2]
 输出: 3
 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
 
 */
class MaxProfit: NSObject {
    
    /*
     采用动态规划的思想
     我们可以设置f[i]表示第i天结束后的”累计最大收益“。根据题目描述，我们会有三种状态。
     我们定义各个状态对应的表达式
     1: 持有股票。此时对应的收益记为  f[i][0]
     2: 不持有股票，但是处在冷冻期。  f[i][1]
     3: 不持有股票，且不处于冷冻期。  f[i][2]
     
     这里的「处于冷冻期」指的是在第 i 天结束之后的状态。也就是说：如果第 i 天结束之后处于冷冻期，那么第 i+1 天无法买入股票。
     
     我们对每种状态进行状态转移。
     如何进行状态转移呢？在第 i 天时，我们可以在不违反规则的前提下进行「买入」或者「卖出」操作，此时第 i 天的状态会从第 i−1 天的状态转移而来；我们也可以不进行任何操作，此时第 i 天的状态就等同于第 i−1 天的状态。

     对于状态一 f[i][0]
        我们目前持有股票。这支股票可以是昨天买的(f[i-1][0])；
        也可以是当天买的，那么i-1天就不能处于冷冻期，且第i天不处于冷冻期。那么i-1天的收益就是f[i-1][2]，到了今天再减去当天股价price[i]
     可得出  f[i][0] = max(   f[i-1][0],  f[i-1][2]-price[i]  )
     
     
     对于状态二 f[i][1]
        我们不持有股票，但是处在冷冻期。表明我们在今天做了卖出的操作，则第i-1天必然持有股票。对应的收益就是f[i-1][0]，再加上今天卖股票的收益price[i]
     可得出  f[i][1] = f[i-1][0]+price[i]
     
     对于状态三
        我们不持有股票，且不在冷冻期。
        说明当天没有任何操作，即i-1天结束时不持有任何股票：如果处于冷冻期，对应的状态为f[i-1][1]；如果不处于冷冻期，对应的状态为f[i-1][2]。
     可得出  f[i][2] = max(    f[i-1][1] ,  f[i-1][2])
     
     
     
     从而 如果一共有n天 那么我们的结果就是 max(  f[n-1][0],    f[n-1][1],  f[n-1][2] )
     如果最后一天仍然持有股票 则对于本题是无意义的 因此有 max(  f[n-1][1],  f[n-1][2] )
     
     
     边界条件：
     我们可以将第0天的情况作为动态规划中的边界条件：
     f[0][0] = -price[0]
     f[0][1] = 0
     f[0][2] = 0
     
     在第0天 如果持有股票，那么一定是当天买入的，收益就是负的当天股价。
     其余情况不持有股票收益都可以置为0
     
     这样我们就可以从第1天开始，根据状态转移方程进行动态规划，直到计算出n-1天的结果
     
     */
    
    func maxProfit(_ prices: [Int]) -> Int {
        
        guard prices.count != 0 else {
            return 0
        }
        
        let days = prices.count
        
        var f = [[Int]](repeating: [Int](repeating: 0, count: 3), count: days)
        f[0][0] = -prices[0]
        
        for i in 1 ..< days {
            f[i][0] = max(f[i-1][0], f[i-1][2] - prices[i])
            f[i][1] = f[i-1][0] + prices[i]
            f[i][2] = max(f[i-1][2], f[i-1][1])
        }
        return max(f[days-1][1], f[days-1][2])
    }
}
